#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* tail, * cur;
    cur = tail = head;
    int n1 = 0, n2 = 0;
    while (tail)
    {
        n1++;
        tail = tail->next;
    }
    while (n2 < n1 / 2)
    {
        n2++;
        cur = cur->next;
    }
    return cur;
}
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
    struct ListNode* tail, * cur;
    cur = tail = pListHead;
    int n = 0, m = 0;
    while (tail)
    {
        n++;
        tail = tail->next;
    }
    if (n < k)
    {
        return NULL;
    }
    while (m < n - k)
    {
        m++;
        cur = cur->next;
    }
    return cur;
}

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* prev, * tail;
    tail = prev = (struct ListNode*)malloc(sizeof(struct ListNode));
    prev->next = NULL;
    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            tail->next = list1;
            tail = tail->next;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            tail = tail->next;
            list2 = list2->next;
        }
    }
    if (list1)
        tail->next = list1;
    if (list2)
        tail->next = list2;
    struct ListNode* newhead = prev->next;
    free(prev);
    return newhead;
}